package dp_algorithm.nowcoder.medium;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author bruin_du
 * @description 查找两个字符串a,b中的最长公共子串
 * https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?
 * tpId=37&&tqId=21288&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 * @date 2022/5/16 20:40
 **/
public class LongestCommonString {
    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                String str1 = in.next();
                String str2 = in.next();
                String shortStr = str1.length() > str2.length() ? str2 : str1;
                String longStr = str1.length() > str2.length() ? str1 : str2;
                //推荐方法：动态规划
                System.out.println(getLCStringWithDP(shortStr, longStr));

                //循环遍历的方法
                System.out.println(getLCString(shortStr, longStr));
            }
        }

    public static String getLCStringWithDP(String shortStr,String longStr){
        char[] shortArr = shortStr.toCharArray();
        char[] longArr = longStr.toCharArray();
        //dp的每个元素保存的是短字符串的前i个字符和长字符串的前j个字符的最长公共子串的长度
        //为了方便计算,还是将数组的大小扩大
        int[][] dp = new int[shortArr.length + 1][longArr.length + 1];
        //保存最长的字符串的长度和开始的位置索引
        int maxLength = 0,startIndex = 0;
        for (int i = 1; i <= shortArr.length; i++) {
            for (int j = 1; j <= longArr.length; j++) {
                if(shortArr[i - 1] == longArr[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //有新的公共子串长度大于记录的,就更新
                    if(dp[i][j] > maxLength){
                        maxLength = dp[i][j];
                        startIndex = i - maxLength;
                    }
                }
            }
        }
        return shortStr.substring(startIndex,startIndex + maxLength);
    }

    public static String getLCString(String shortStr,String longStr){
        int longLength = longStr.length();
        int shortLength = shortStr.length();
        Set<Character> set = new HashSet<>();
        String retStr = "";
        //注意,这里得入长的字符串,因为要保证多个公共字符串长度相同的时候
        //取在短字符串中最先出现的那个
        for (int i = 0; i < longLength; i++) {
            set.add(longStr.charAt(i));
        }
        for (int i = 0; i < shortLength; i++) {
            char chS = shortStr.charAt(i);
            if (set.contains(chS)) {
                int indexOfLongStr = 0;
                int pIndexOfL;
                while ((pIndexOfL = longStr.indexOf(chS, indexOfLongStr)) != -1) {
                    StringBuilder sb = new StringBuilder();
                    int pIndexOfS = i;
                    while (pIndexOfS < shortLength && pIndexOfL < longLength &&
                            shortStr.charAt(pIndexOfS) == longStr.charAt(pIndexOfL)) {
                        sb.append(shortStr.charAt(pIndexOfS));
                        pIndexOfS++;
                        pIndexOfL++;
                    }
                    if (sb.length() > retStr.length())
                        retStr = sb.toString();
                    indexOfLongStr++;
                }
            }
        }
        return retStr;
    }
}
